#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    public:
        ListNode *swapPairs(ListNode *head) {
            if (!head || !head->next) return head;
            ListNode dummy(0);
            dummy.next = head;
            ListNode *pre = &dummy, *cur = head, *next = head->next;
            while (next) {
               ListNode *tmp = next->next; 
               //cout <<"Cur: " << cur->val << endl;
               pre->next = next;
               next->next = cur;
               pre = cur;
               cur = tmp;
               if (tmp) next = tmp->next;
               else break;
            }
            pre->next = cur;
            return dummy.next;
        }
};

//add better code
      ListNode *swapPairs(ListNode *head) {
          ListNode Dummy(0);
          ListNode *h = &Dummy;
          h->next = head;
          ListNode *pre = h, *cur = head;
          while(cur && cur->next) {
             // pre->next = cur->next;
              ListNode *next = cur->next->next;
              pre->next = cur->next;
              cur->next->next = cur;
              cur->next = next;
              pre = cur;
              cur = next; 
          }   
          return h->next;
      }  

ListNode *newList(int data[], int index, int size)
{
    ListNode *node = NULL;
    if (index == size)
        return node;

    node = new ListNode(data[index]);
    node->next = newList(data, index+1, size);

    return node;
}

//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{

    Solution mySolution;
    cout << "-----------------Test 1--------------------" << endl;
    vector<ListNode *> myList;
    int data[] = {1,2,3,4,5,6,7,8,9};
    ListNode *list1, *list2;
    list1 = newList(data, 0, sizeof(data)/sizeof(int));
    ListNode *list = mySolution.swapPairs(list1);
    while(list) {
        cout << list->val << " ";
        getchar();
        list= list->next;
    }
    cout << endl;
    cout << "-----------------Test 2--------------------" << endl;

    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
